/*
练习7-2 判断两点是否连通
分数 25
作者 陈越
单位 浙江大学

给定稀疏有向图 graph 中任意两点 u 和 v，请判断是否存在从 u 到 v 的路径。
函数接口定义：

bool ExistPath( LGraph graph, Vertex u, Vertex v );

其中邻接表表示的图 LGraph 的结构定义定义如下：

typedef enum { false, true } bool;
typedef int Vertex;    // 顶点编号类型
typedef char VertInfo; // 顶点信息类型
typedef struct EdgeNode *Position; // 指针即结点位置
struct EdgeNode {
    Vertex dest;     // 边的另一端点编号
    Position next;   // 线性表中下一个元素的位置
};

typedef struct HeadNode *AdjList; // 邻接表
struct HeadNode {
    Position adj;  // 邻接表头指针
    VertInfo data; // 存储顶点信息
};

typedef struct LGraphNode *LGraph; // 邻接表表示的图
struct LGraphNode {
    int n_verts; // 顶点数
    int m_edges; // 边数
    AdjList *ver_list; // 存储顶点邻接表
    bool directed; // true为有向图，false为无向图
};

ExistPath 判断是否存在从 u 到 v 的路径，如果是则返回 true，否则返回 false。
裁判定义的测试用主函数通过读入顶点数、边数、以及每条边的两个端点来建立一个图，
随后读入若干对顶点 u 和 v 的编号（从 0 开始）并调用 ExistPath
进行判断，最后根据判断结果输出 Yes 或 No。

输入样例：

6 9
0 1
0 2
0 3
1 2
2 3
1 4
3 4
3 5
4 5
3
0 5
3 1
5 0

输出样例：

Yes
No
No
*/

#include <stdio.h>
#include <stdlib.h>

/* 邻接表表示的图定义 */
typedef enum { false, true } bool;
typedef int Vertex;                /* 顶点编号类型 */
typedef char VertInfo;             /* 顶点信息类型 */
typedef struct EdgeNode *Position; /* 指针即结点位置 */
struct EdgeNode {
    Vertex dest;   /* 边的另一端点编号 */
    Position next; /* 线性表中下一个元素的位置 */
};
typedef struct HeadNode *AdjList; /* 邻接表 */
struct HeadNode {
    Position adj;  /* 邻接表头指针 */
    VertInfo data; /* 存储顶点信息 */
};
typedef struct LGraphNode *LGraph; /* 邻接表表示的图 */
struct LGraphNode {
    int n_verts;       /* 顶点数 */
    int m_edges;       /* 边数 */
    AdjList *ver_list; /* 存储顶点邻接表 */
    bool directed;     /* true为有向图，false为无向图 */
};
#define kMaxV 1000
/* 裁判实现，细节略 */
void InitGraph(LGraph graph, int kMaxVertex, bool directed);
bool ExistEdge(LGraph graph, Vertex u, Vertex v);
void InsertEdge(LGraph graph, Vertex u, Vertex v);
LGraph BuildGraph();
/* 裁判实现部分结束 */

bool ExistPath(LGraph graph, Vertex u, Vertex v);

int main(void) {
    LGraph graph;
    int k, i;
    Vertex u, v;

    graph = BuildGraph();
    scanf("%d", &k);
    for (i = 0; i < k; i++) {
        scanf("%d %d", &u, &v);
        if (ExistPath(graph, u, v) == true) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }

    return 0;
}
/* 你的代码将被嵌在这里 */

bool DFS(LGraph graph, Vertex u, Vertex v, bool visited[]) {
    if (u == v) {
        return true;
    }
    visited[u] = true;
    for (Position p = graph->ver_list[u]->adj; p != NULL; p = p->next) {
        if (!visited[p->dest]) {
            if (DFS(graph, p->dest, v, visited)) {
                return true;
            }
        }
    }
    return false;
}

bool ExistPath(LGraph graph, Vertex u, Vertex v) {
    bool visited[kMaxV] = {false};
    return DFS(graph, u, v, visited);
}